package demo.hw;

public class _数组连续和 {
    public static void main(String[] args) {
        /**
         * 给定一个含有N个正整数的数组，求出有多少个连续区间（包括单个正整数），它们的和大于等于x。
         * 输入描述
         * 第一行两个整数N x（0 < N <= 100000, 0 <= x <= 10000000)
         * 第二行有N个正整数（每个正整数小于等于100)。
         * 输出描述
         * 输出一个整数，表示所求的个数。
         *
         * 示例1
         * 输入
         * 3 7
         * 3 4 7
         * 输出[3,4],[3,4,7],[4,7],[7]
         * 4
         * 示例2
         * 输入
         * 10 10000000
         * 1 2 3 4 5 6 7 8 9 10
         * 输出
         * 0
         *
         * 核心算法逻辑
         * 1.滑动窗口：使用left和right指针表示当前窗口
         * 2.动态维护窗口和：sum记录当前窗口内元素的和
         * 3.高效计数：当窗口[left, right]满足条件时，所有[left, right], [left, right+1], ..., [left, n-1]都满足条件
         */
        int[] nums = {3, 4, 7};
        int n = nums.length;
        int x = 7;

        int left = 0;// 滑动窗口左边界
        int sum = 0;// 当前窗口的和
        int count = 0; // 统计满足条件的区间个数
        for (int right = 0; right < n; right++) {
            sum += nums[right]; // 将右边界元素加入当前和
            // 当当前窗口和大于等于x时，移动左边界并计数
            while (left <= right && sum >= x) {
                // 关键步骤：一旦[left, right]满足条件，那么所有以left开头，
                // 从right到数组末尾的区间都满足条件
                count += (n - right);
                sum -= nums[left]; // 移动左边界，缩小窗口
                left++;
            }
        }
        System.out.println(count);
    }
}
